/**
 * https://leetcode-cn.com/problems/palindromic-substrings/
 * 回文子串的数目
 * @param s 
 */
const countSubstrings = (s: string): number => {
    if (s === '') return 0

    let ans = 0
    const len = s.length;
    const dp: number[] = new Array(len).fill(0)

    for (let i = len - 1; i >= 0; i--) {
        // 每一个字母都是一个回文子串
        ans++;

        // 默认是1
        dp[i] = 1
        let cur = 0;

        for (let j = i + 1; j < len; j++) {
            let leftBottom = cur;

            // 作为下次循环的左下角
            cur = dp[j]

            if (s[j] === s[i]) {
                let curNum = 1

                // 判断中间是不是回文子串
                if (j - i == 1) {
                    // 是回文子串
                    ans++;
                    curNum = 2;
                } else if (j - i - 1 === leftBottom) {
                    // 中间是回文子串
                    ans++
                    curNum = leftBottom + 2
                }

                // 更新dp
                dp[j] = curNum
            } else {
                dp[j] = 1;
            }
        }
    }
    return ans
};


console.log(countSubstrings("aaaaa"))